package 数据结构OJ;

/**
 * @author shy_black
 * @date 2019/3/31 19:45
 * @Description:
 */

public class 树的子结构 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

        public class Solution {
            public boolean HasSubtree(TreeNode root1, TreeNode root2) {
                boolean result = false;
                if (root1 != null && root2 != null) {
                    if (root1.val == root2.val) {
                        result = DoesTree1HaveTree2(root1, root2);
                    }
                    if (!result) {
                        result = HasSubtree(root1.left, root2);
                    }
                    if (!result) {
                        result = HasSubtree(root1.right, root2);
                    }
                }
                return result;
            }

            public boolean DoesTree1HaveTree2(TreeNode root1, TreeNode root2) {
                if (root1 == null && root2 != null) return false;
                if (root2 == null) return true;
                if (root1.val != root2.val) return false;
                return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
            }
        }
    }
}